#!/usr/bin/env python
# _*_coding:utf-8_*_

"""
算法模板
@Time : 2022/2/17 13:06
@Author: RunAtWorld
@File: alog_template.py
"""
import collections


def binary_search(arr, target):
    """
    二分搜索模板
    寻找一个数（基本的二分搜索）
    """
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
    return -1


def binary_search_left_bound(arr, target):
    """
    二分搜索模板
    寻找左侧边界的二分搜索, 左闭右开
    """
    left = 0
    right = len(arr)  # 注意
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            right = mid  # 注意
        elif arr[mid] > target:
            right = mid
        elif arr[mid] < target:
            left = mid + 1
    # 判断target小于最小值或大于最大值
    if left >= len(arr) or arr[left] != target:
        return -1
    return left


def binary_search_right_bound(arr, target):
    """
    二分搜索模板
    寻找右侧边界的二分搜索, 左闭右开
    """
    left = 0
    right = len(arr)  # 注意
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            left = mid + 1  # 注意
        elif arr[mid] > target:
            right = mid
        elif arr[mid] < target:
            left = mid + 1
    # 判断target小于最小值或大于最大值
    if right == 0 or arr[right - 1] != target:
        return -1
    return right - 1


def slidingWindow(src: str, target: str):
    """
    滑动窗口模板
    以 力扣76.最小覆盖子串 为例
    """
    need, window = collections.defaultdict(int), collections.defaultdict(int)
    valid = 0
    left = right = 0
    for c in target:
        need[c] += 1

    substr_len = len(src) + 1
    substr_start = 0
    while right < len(src):
        c = src[right]
        right += 1
        # 窗口数据更新
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1

        # 缩小左窗口
        while valid == len(need):
            if right - left < substr_len:
                substr_start = left
                substr_len = right - left
            d = src[left]
            left += 1
            # 窗口数据更新
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
        return src[substr_start:substr_start + substr_len] if substr_len != len(src) + 1 else ""


def solveNQueens(n: int):
    """
    回溯模板
    以 51. N皇后 为例
    """
    res = []
    N = n

    def generate_board(track):
        output = []
        for i in range(N):
            output.append("".join(track[i]))
        return output

    def backtrack(track, row):
        # track是路径,row是行选择
        if row == N:
            # 满足结束条件
            res.append(generate_board(track[:]))
            return
        for j in range(len(track[row])):
            # j是列选择
            if not is_valid(track, row, j):
                continue
            # 做选择
            track[row][j] = 'Q'
            backtrack(track, row + 1)
            # 撤销选择
            track[row][j] = '.'

    def is_valid(track, row, col):
        # 判断行和列冲突
        for i in range(row):
            for j in range(N):
                if track[i][j] == 'Q' and (i == row or j == col):
                    return False
        # 判断左上冲突
        for i in range(1, row + 1):
            if row - i >= 0 and col - i >= 0 and track[row - i][col - i] == 'Q':
                return False
        # 判断右上冲突
        for i in range(1, row + 1):
            if row - i >= 0 and col + i < N and track[row - i][col + i] == 'Q':
                return False
        return True

    track = [['.'] * N for _ in range(N)]
    backtrack(track, 0)
    return res


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def bitree_bfs_que(root: TreeNode):
    """
    借助队列完成二叉树bfs
    """
    if not root:
        return
    que = [root]
    while que:
        size = len(que)
        for i in range(size):
            node = que.pop(0)
            # 访问 node
            print(node.val, end=',')
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)


def bitree_bfs_recusive(root: TreeNode):
    """
    递归完成二叉树bfs
    利用dfs的递归，在递归过程中记录每个node的level，将属于一个level的node放入同一list
    """
    if not root:
        return
    res = []

    def travel(root: TreeNode, level: int, res_list):
        if not root:
            return
        if level >= len(res_list):
            res_list.append([root])
        else:
            res_list[level].append(root)
        travel(root.left, level + 1, res_list)
        travel(root.right, level + 1, res_list)

    travel(root, 0, res)
    for li in res:
        for n in li:
            # 访问节点
            print(n.val, end=',')


def bitree_dfs_recursive(root: TreeNode):
    """
    递归完成二叉树dfs
    """
    if not root:
        return
    print(root.val, end=',')
    bitree_dfs_recursive(root.left)
    bitree_dfs_recursive(root.right)


def bitree_dfs_stack(root: TreeNode):
    """
    借助stack完成二叉树dfs
    """
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val, end=',')
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)


class Node:
    def __init__(self, val):
        self.val = val

    def adj(self):
        return Node


def bfs_common(start: Node, target: Node):
    # 核心数据结构: 队列
    que = list()
    # 避免走回头路
    visited = set()
    # 记录扩散的步数
    step = 0

    que.append(start)
    visited.add(start)
    while que:
        sz = len(que)
        for i in range(sz):
            # 将当前队列中的所有节点向四周扩散
            cur = que.pop(0)
            # 划重点: 这里判断是否到达终点
            if cur == target:
                return step
            for node in cur.adj():
                if node not in visited:
                    que.append(node)
                    visited.add(node)
        # 划重点: 在这里更新步数
        step += 1
